Search for: All records

The distance matrix $$\mathcal{D}(G)$$ of a graph $$G$$ is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is $$\mathcal{D}^L (G)=T(G)-\mathcal{D} (G)$$, where $T(G)$ is the diagonal matrix of row sums of $$\mathcal{D}(G)$$. Several general methods are established for producing $$\mathcal{D}^L$$-cospectral graphs that can be used to construct infinite families. Examples are provided to show that various properties are not preserved by $$\mathcal{D}^L$$-cospectrality, including examples of $$\mathcal{D}^L$$-cospectral strongly regular and circulant graphs. It is established that the absolute values of coefficients of the distance Laplacian characteristic polynomial are decreasing, i.e., $$|\delta^L_{1}|\geq \cdots \geq |\delta^L_{n}|$$, where $$\delta^L_{k}$$ is the coefficient of $x^k$. 

Abstract The concept of branch decomposition was first introduced by Robertson and Seymour in their proof of the Graph Minors Theorem, and can be seen as a measure of the global connectivity of a graph. Since then, branch decomposition and branchwidth have been used for computationally solving combinatorial optimization problems modeled on graphs and matroids. General branchwidth is the extension of branchwidth to any symmetric submodular function defined over a finite set. General branchwidth encompasses graphic branchwidth, matroidal branchwidth, and rankwidth. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. It was shown in [I. V. Hicks. Graphs, branchwidth, and tangles! Oh my!Networks, 45:55‐60, 2005] that a tangle basis of orderkis coextensive to a tangle of orderk. In this paper, we revisit the construction of tangle bases computationally for other branchwidth parameters and show that the tangle basis approach is still competitive for computing optimal branch decompositions for general branchwidth.